/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年05月06日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>
using namespace std;


class Solution {
public:
    int dir[4][2]={{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if( m == 0 )
            return 0;
        int n = matrix[0].size();
        
        int** dp = new int*[m];
        int maxres = 1, tmpres = 0;
        
        for(int i = 0; i < m; i++){
            dp[i] = new int[n];
            for(int j = 0; j < n; j++)
                dp[i][j] = 0;
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                tmpres = dfs(matrix, dp, i, j);
                maxres = max(tmpres, maxres);
            }
        }

        for(int i =0; i < m; i++){
            delete[] dp[i];
        }
        delete[] dp;

        return maxres;
    }

private:
    int dfs(vector<vector<int>>& matrix, int** dp, int i, int j){
        if(dp[i][j] > 0)
            return dp[i][j];
    
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = 0;
        int len = 0, maxres = 1;

        for(int k = 0; k < 4; k++){
            x = dir[k][0] + i;
            y = dir[k][1] + j;
            if(x < 0 || x >= m || y < 0|| y>= n || matrix[i][j] >= matrix[x][y])
                continue;
            len = 1 + dfs(matrix, dp, x, y);
            maxres = max(maxres, len);
        }
        
        dp[i][j] = maxres;
        return maxres;
    }
    
};
